递归和动态规划——汉诺塔问题

Posted on | In ,

Hanio汉诺塔问题：将所有的盘子从塔A移到塔C，且每次移动一个盘子，上面的盘子比下面的盘子大。

实现：利用递归。无论有多少个盘子，都将其看做只有两个盘子。
假设有 N 个盘子在塔座A上，将其看做两个盘子，其中第(N-1)1个盘子看成是一个盘子，最下面第N个盘子看成是一个盘子，那么解决办法为：
①、先将A塔座的第(N-1)1个盘子看成是一个盘子，放到中介塔座B上，然后将第N个盘子放到目标塔座C上。
②、然后A塔座为空，看成是中介塔座，B塔座这时候有N-1个盘子，将第(N-2)~1个盘子看成是一个盘子，放到中介塔座A上，然后将B塔座的第(N-1)号盘子放到目标塔座C上。
③、这时候A塔座上有(N-2)个盘子，B塔座为空，又将B塔座视为中介塔座，重复①，②步骤，直到所有盘子都放到目标塔座C上结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Hanio {
	/**
	 * @param n 盘子的总数
	 * @param from 初始塔座
	 * @param mid 中介塔座
	 * @param to 目标塔座
	 */
	public static void move(int n, String from, String mid, String to) {
		if (n == 1) {
			System.out.println("将盘子" + n + "从塔座" + from + "移动到目标塔座" + to);
		} else {
			move(n-1, from, to, mid); //(N-1~1) : A->B, N : A->C
			System.out.println("将盘子" + n + "从塔座" + from + "移动到目标塔座" + to);
			move(n-1, mid, from, to); //(N-2~1) : B->A, N-1 : B->C
		}
	}
	public static void main(String[] args) {
		move(3, "A", "B", "C");
	}
}